// Copyright (c) 2012 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.
//
// A filter block is stored near the end of a Table file.  It contains
// filters (e.g., bloom filters) for all data blocks in the table combined
// into a single filter block.

#ifndef STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
#define STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_

#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>

#include "leveldb/slice.h"
#include "util/hash.h"

namespace leveldb {

class FilterPolicy;

// A FilterBlockBuilder is used to construct all of the filters for a
// particular Table.  It generates a single string which is stored as
// a special block in the Table.
//
// The sequence of calls to FilterBlockBuilder must match the regexp:
//      (StartBlock AddKey*)* Finish
class FilterBlockBuilder {
 public:
  explicit FilterBlockBuilder(const FilterPolicy*);

  FilterBlockBuilder(const FilterBlockBuilder&) = delete;
  FilterBlockBuilder& operator=(const FilterBlockBuilder&) = delete;

  void StartBlock(uint64_t block_offset);
  void AddKey(const Slice& key);
  Slice Finish();  // 生成一个元数据块，并分别写入布隆过滤器的内容、偏移量、内容总大小和基数。

 private:
  void GenerateFilter();

  const FilterPolicy* policy_;   // 实现了FilterPolicy接口的类，在布隆过滤器中为BloomFilterPolicy。
  std::string keys_;             // 生成布隆过滤器的键，注意keys_类型为string，此处会将所有的键依次追加到keys_中，例如有3个键：level、level1和level2，则keys_为levellevel1level2。
  std::vector<size_t> start_;    // 数组类型，保存keys_参数中每一个键的offset，例如上述例子中keys_为levellevel1level2，start_数组中保存的值为0、5、11，通过start_能够拆分出具体的键分别为level、level1、level2。
  std::string result_;           // 保存生成的布隆过滤器内容。
  std::vector<Slice> tmp_keys_;  // 生成布隆过滤器时，会通过keys_和start_拆分出每一个键，将拆分出的每一个键保存到tmp_keys_数组中。
  std::vector<uint32_t> filter_offsets_;  // result_中每个过滤器偏移量。
};

class FilterBlockReader {
 public:
  // REQUIRES: "contents" and *policy must stay live while *this is live.
  FilterBlockReader(const FilterPolicy* policy, const Slice& contents);
  bool KeyMayMatch(uint64_t block_offset, const Slice& key);

 private:
  const FilterPolicy* policy_;  // 实现了FilterPolicy接口的类，在布隆过滤器中为BloomFilterPolicy。
  const char* data_;    // 指向元数据块的开始位置。
  const char* offset_;  // 指向元数据块中过滤器偏移量的开始位置。
  size_t num_;          // 过滤器偏移量的个数。
  size_t base_lg_;      // 过滤器基数。
};

}  // namespace leveldb

#endif  // STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
